\documentclass[UTF8]{ctexart}
\usepackage{listings} 
\usepackage{xcolor}
\usepackage{fancyhdr}%设置页脚页眉需要的包
\pagestyle{fancy}
\usepackage{graphicx}
\usepackage{cite}
\usepackage{tikz}
\usepackage{booktabs}
\usepackage{float}
\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{xeCJK}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{gnuplottex}
\usepackage{geometry}
\usepackage{enumitem}
\usepackage{verbatimbox}
\usepackage{amsfonts,amssymb} 
\usepackage[ruled,linesnumbered]{algorithm2e}
\usepackage[colorlinks,linkcolor=blue,citecolor=blue]{hyperref}
\usepackage{cite}
\CTEXsetup[format={\Large\bfseries}]{section}
\newtheorem{example}{例}             % 整体编号
\newtheorem{theorem}{定理}[section]  % 按 section 编号
\newtheorem{definition}{定义}
\newtheorem{axiom}{公理}
\newtheorem{property}{性质}
\newtheorem{proposition}{命题}
\newtheorem{lemma}{引理}
\newtheorem{corollary}{推论}
\newtheorem{remark}{注解}
\newtheorem{condition}{条件}
\newtheorem{conclusion}{结论}
\newtheorem{assumption}{假设}
\newcommand{\enabstractname}{Abstract}
\newenvironment{enabstract}{%
    \par\small
    \noindent\mbox{}\hfill{\bfseries \enabstractname}\hfill\mbox{}\par
    \vskip 2.5ex}{\par\vskip 2.5ex}
\usetikzlibrary{positioning, shapes.geometric}
\lstset{
  language=C++,
  frame=shadowbox,
  rulesepcolor=\color{red!20!green!20!blue!20},
  keywordstyle=\color{blue!90}\bfseries,
  commentstyle=\color{red!10!green!70}\textit,
  showstringspaces=false,
  numbers=left,
  numberstyle=\tiny,
  stringstyle=\ttfamily,
  breaklines=true,
  extendedchars=false,
  texcl=true}

\title{Theoretical Assignment II}

\author{韩骐骏 \\ (数学科学学院)信息与计算科学3200103585}

\begin{document}

\maketitle

\section{Problem 2.9.2 A}
\subsection{Project requirements}
Implement the Newton formula in a subroutine that produces the value of the interpolation polynomial $p{\mbox{\scriptsize n}}(f;x{\mbox{\scriptsize 0}},x{\mbox{\scriptsize 1}},...,x{\mbox{\scriptsize n}};x)$ at any real $x$, where $n\in N{\mbox{\scriptsize +}}$, $x{\mbox{\scriptsize i}}$’s are distinct, and $f$ is a function assumed to be available in the form of a subroutine.\\

\subsection{Designing thinking}
A basic idea is to use a vector to store the coefficients of the polynomials you want to fit, and use it to when necessary. We can also choose to use nested multiplication to calculate the values immediately when writing classes for interpolation functions, but this means that only the first evaluation can be faster, so there is no great significance to write more $operator()$ functions.\\
First, we provide a base class Function, in which we provide a virtual function $operator()$, so that when writing Newton interpolation class and Hermite interpolation class, we can directly add $operator()$ to them to calculate values (although we did not do so). In addition, two functions are provided in the Function class to numerically calculate the first derivative and the second derivative. Although this project requires us to write a function that can accurately derive the polynomial, I believe that if the order of the fitted polynomial is too high, the derivative may be maximum at some point. Therefore, using numerical differentiation may "soften" the derivative function to make it more smooth.\\
Then we wrote the Polynomial class, which has a protected member integer $order$ and a vector $coef$ to store the order and coefficients of polynomials, respectively. In public members, in addition to some basic constructors (including two functions used to generate constant polynomials and first-order polynomials respectively), we also overload some operators such as $(),<<,+, -, *$, which are used for basic operations between polynomials and polynomials or between polynomials and constants. Originally, I wanted to find all the approximate zeros of the polynomial with the help of Newton's method in the first programming operation, and then approximate the polynomial as the product of some linear expressions related to the zeros. This can quickly improve the speed of evaluation, but unfortunately, the time is not enough. In addition, the $diff()$ function is defined to solve the exact derivative of the polynomial, which is output in Polynomial format.\\
Finally, in this header file, we have compiled two interpolation classes: Newton class and Hermite class. They all have three private members $x, y, diff\_table$, the first two are used to store the coordinates of the points to be interpolated, $diff\_table$ is the difference table. The remaining constructors and generating polynomial functions are written according to the theory in the book, and will not be repeated here. It is worth mentioning that when writing Hermite interpolation class, I added an additional vector variable $d\_o$ for its private members and function parameters $d\_o$，which represents the derivative order of $y$ corresponding to $x$.\\

\end{document}
